The need to control systems comprising many items, where each item requires scheduling of actions and allocation of resources over time, arises in a variety of technological, industrial, and economic areas.
In a manufacturing plant production of parts requires the scheduling of operations by the allocation of machines.
In a city traffic system, vehicles require the use of roads and intersections to proceed from source to destination.
In a communication network, messages require bandwidths and buffer storage for transmission between nodes.
In multi-project scheduling one needs to allocate shared resources and determine timing of activities.
In an economic system availability of inputs and demand for outputs have to be matched by scheduling and allocation of production capacity.
Methods used to control such systems are mostly of two kinds: Some are concerned with local optimization of a small part of the system, others, which view the whole system are ad-hoc methods, which are unable to find optimal solutions. One technique which is commonly used to model such systems is simulation, in which the predicted behavior of the system over time for a particular choice of the controls is calculated. This method is slow, cumbersome, and expensive. Simulation is also used to explore various alternative control choices, in order to choose a good one. However, owing to the complexity of said systems, this method cannot find optimal controls.
What is needed is a general unified method for the control of systems as described above, which models the system as a whole, and which optimizes the whole system.
There are two broad theoretical approaches to these control problems: Formulation of the problem for a finite time horizon as a detailed discrete optimization problem, and formulation of an infinite horizon steady state stochastic optimization problem. Both approaches are often inadequate to handle problems of the size that arises in practice. Furthermore, each approach has a grave conceptual fault: In a finite horizon detailed discrete optimization one needs to use precise data for the entire time horizon, whereas in reality only data of the current state is accurate. As a result the quality of the derived controls degrades with time. Optimization of the steady state of a stochastic system assumes that the system operates under stationary conditions long enough to reach a steady state, and this is almost never the case.
What is needed is a method which takes the middle way between the two approaches, by optimizing the system over a finite time horizon, where only on-line decision rules are considered, wherein such on-line decision rules are characterized by the fact that they use the state of the system at the decision moment, and do not require detailed information for the whole time horizon.
One approach which has not been used in the control of said systems is Continuous Linear Programming.
Continuous Linear Programming (CLP) problems were introduced by Richard Bellman in 1953, in his paper “Bottleneck problems and dynamic programming”, Proceeding of the National Academy of Science 39:947-951, in the context of economic input output systems. E. J. Anderson introduced in his 1981 paper “A new continuous model for job-shop scheduling” International Journal of Systems Science 12:1469-1475, a sub-class of CLP, which he called Separated Continuous Linear Programming (SCLP) problems, in the context of job shop scheduling. Major progress in the theory of SCLP was achieved by M. C. Pullan in his paper “An algorithm for a class of continuous linear programs” SIAM Journal of Control and Optimization 31:1558-1577, and in subsequent papers, in which he formulated a dual problem and proved strong duality under some quite general assumptions. However, research to date has failed to produce efficient algorithms for the solution of CLP and SCLP problems. The main difficulty in finding an efficient algorithm is that candidate solutions as well as the optimal solution are functions of time, which have an infinite uncountable number of values for a continuum of times. What is lacking in the prior art is a concise finite description of such functions.
The prior art method to solve CLP or SCLP is to discretize the problem, so as to obtain an approximation by a standard linear program, which is then solved by a standard linear programming algorithm. This method is far from satisfactory for the following three reasons: First, it does not give an exact solution. Second, the resulting linear program is very large. Third, the solution of the linear program, by its discrete nature, obscures many important features of the optimal solution of the CLP or SCLP. As a result of these three shortcomings, only small problems can be solved, and the quality of the solution is poor.
Lack of an efficient algorithm for CLP or SCLP is the reason that continuous linear programming models have not been used until now to control complex practical systems. What is needed is an efficient and accurate algorithm for the solution of CLP and SCLP.
Graphical representations have always been of extreme importance for decision makers. An example of this is the Gantt Chart, for job-shop scheduling, introduced by Henry Laurence Gantt during first world war and still used today. The use of computers to display such graphics has greatly enhanced their effectiveness. Furthermore, they can often be used interactively through a graphic user interface (GUI). There is currently no such graphic representation which is used in the control of said systems. What is needed is a graphic representation which gives in a single view a complete picture of the whole system over the whole time horizon of operation.
Close theoretical connections have been established between some fluid models and the behavior of stochastic systems comprising a plurality of items, see J. G. Dai “On positive Harris recurrence of multi-class queueing networks, a unified approach via fluid limit models” Annals of Applied Probability 5:49-77, 1995, and S. P. Meyn “The policy improvement algorithm for Markov decision processes with general state space”, IEEE Transactions on Automatic Control AC-42:191-196, 1997. These results provide some theoretical motivation for the use of fluid models. What is needed is a method to translate fluid models into actual controls of a real system.